//给你一个字符串 s，找到 s 中最长的 回文 子串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
//
// Related Topics 双指针 字符串 动态规划 👍 7815 👎 0

import enums.Way;

/**
 * 最长回文子串
 */
public class LongestPalindrome {

    public static String longestPalindrome(String s, Way way) {
        if (s == null || s.isEmpty()) {
            return "";
        }
        switch (way) {
            case WAY1:
                return way1(s);
            case WAY2:
                return way2(s);
            default:
                throw new IllegalArgumentException("Way is not exist.");
        }
    }

    /**
     * 动态规划：用二维数组表示从i到j的字符串是否为回文
     * 时间复杂度：O(n²)
     * 空间复杂度：O(n²)
     */
    private static String way1(String s) {
        int length = s.length();
        int maxLength = 1;
        int begin = 0;
        boolean[][] array = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            array[i][i] = true;
        }
        for (int leftBorder = 2; leftBorder <= length; leftBorder++) {
            for (int left = 0; left < length; left++) {
                int right = leftBorder + left - 1;
                if (right >= length) {
                    break;
                }
                if (s.charAt(left) == (s.charAt(right))) {
                    if (right - left < 3) {
                        array[left][right] = true;
                    } else {
                        array[left][right] = array[left + 1][right - 1];
                    }
                } else {
                    array[left][right] = false;
                }
                if (array[left][right] && right - left + 1 > maxLength) {
                    maxLength = right - left + 1;
                    begin = left;
                }
            }
        }
        return s.substring(begin, begin + maxLength);
    }

    /**
     * 中心扩展法：依次遍历字符串，并计算以i为中间点，向两边扩展的回文子串的长度
     * 时间复杂度：O(n²)
     * 空间复杂度：O(1)
     */
    private static String way2(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
//            计算aba的情况
            int len1 = expandAroundCenter(s, i, i);
//            计算abba的情况
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    private static int expandAroundCenter (String s,int left, int right){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}
